/*
 * https://leetcode-cn.com/problems/sliding-puzzle/
 * bfs 查找滑动最少次数问题
 */
typedef struct {
    char str[7];
    UT_hash_handle hh;
} ut_hash_t;
ut_hash_t *visited_map = NULL;
void swap(char *a, char *b)
{
    char c = *a;
    *a = *b;
    *b = c;
}
int slidingPuzzle(int** board, int boardSize, int* boardColSize){
    visited_map = NULL;
    char board_str[7] = "000000";
    char target[7] = "123450";
    for (int x = 0; x < 2; x++) { // 2行
        for (int y = 0; y < 3; y++) { // 3 列
            board_str[x*3 + y] = board[x][y] + '0';
        }
    }
    // 0 1 2 
    // 3 4 5
    int neighbor[6][3] = {{1, 3, -1}, {0, 4, 2}, {1, 5, -1}, {0, 4, -1}, {3, 1, 5}, {4, 2, -1}};
    char que[5000][7] = {0};
    int res = 0;
    int start = 0;
    int cnt = 1;
    int end = 1;
    strcpy(que[0], board_str);
    ut_hash_t *s = (ut_hash_t *)malloc(sizeof(ut_hash_t));
    strcpy(s->str, board_str);
    HASH_ADD_STR(visited_map, str, s); // 添加到已访问
    while (start < cnt) {
        for (int i = start; i < end; i++) {
            if (strcmp(que[i], target) == 0) return res; // 达到目的返回
            int index0 = 0;
            while (que[i][index0] != '0')index0++; // 找到0所在的索引
            for (int k = 0; k < 3; k++){ // 遍历3个相邻的索引
                if (neighbor[index0][k] == -1) continue;
                int neighbor_idx = neighbor[index0][k];
                char new_board[7] = {0};
                strcpy(new_board, que[i]);
                swap(&new_board[index0], &new_board[neighbor_idx]); // 与相邻的索引交换
                s = NULL;
                HASH_FIND_STR(visited_map, new_board, s);
                if (s == NULL) {
                    s = (ut_hash_t *)malloc(sizeof(ut_hash_t));
                    strcpy(s->str, new_board);
                    HASH_ADD_STR(visited_map, str, s); // 加入已访问
                    strcpy(que[cnt], new_board); // 加入队列
                    cnt++;
                }
            }
        }
        start = end;
        end = cnt;
        res++;
    }

    return -1;
}